package dataStructure.study.sort;

/**
 * Author: shangsf
 * Date: 2021/4/10 17:44
 * Description:快速排序，时间复杂度O(nlogn)
 * 1.先找第一个元素作为中间元素。然后把小于中间元素的移到左边，把大于中间元素的移到右边
 * 2.递归第1步的动作，直到每部分只有一个元素为止。
 */
public class QuickSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 1) {
            return;
        }
        int n = array.length;

        mergeSort(array,0,n-1);
    }


    static void mergeSort(int[] array,int begin,int end){
        if(begin>=end){
            return;
        }
        int mid= partition(array,begin,end);
        mergeSort(array,begin,mid);
        mergeSort(array,mid+1,end);
    }

    static int partition(int[] array,int begin,int end){
        int mid=array[begin];
        int i=begin+1,j=end;
        while (i<=j){
            if(array[j]<mid){
                int tmp=array[j];
                array[j]=array[i];
                array[i]=tmp;
                i++;
            }else {
                j--;
            }
        }
        array[begin]=array[j];
        array[j]=mid;
        return j;
    }
}
